package codeRandomThoughts.Test213打家劫舍II;

public class Solution2 {
    public int rob(int[] nums) {
        //因为房子是一个环,所以可分成两种情况:
        //1.当我们偷第一家的时候,就不能偷最后一家
        //2.当我们偷最后一家的时候,就不能偷第一家
        //所以分两种情况分别计算能抢的最高金额,然后取最大值即可
        if (nums.length==0) return 0;
        if (nums.length==1) return nums[0];

        int result1 = robByRange(nums, 0, nums.length - 2);
        int result2 = robByRange(nums, 1, nums.length - 1);

        return Math.max(result1, result2);
    }

    //左闭右闭
    public int robByRange(int[] nums, int left, int right) {
        //dp[i]:从下标0-i的房屋中能够偷窃到的最高金额
        int[] dp = new int[right - left + 1];

        if (left == right) return nums[left];
        dp[0] = nums[left];
        dp[1] = Math.max(nums[left], nums[left + 1]);

        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[left + i], dp[i - 1]);
        }

        return dp[dp.length - 1];
    }
}
